package advance.day05;


import java.util.HashMap;

/**
 * 描述：
 *      设计一个缓存结构，初始化时确定其容量，当容量已经满了的情况下再次存储，
 *      先根据LRU策略淘汰内存中的元素
 * @author hl
 * @version 1.0
 * @date 2020/11/10 16:35
 */
public class LRU {
    public static class Node<K, V>{
        K key;
        V value;
        Node pre;
        Node next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    /**
     * 最久未被操作的结点被放在链表的头部，最近被操作的结点放在链表的尾部
     */
    public static class NodeDoubleLinkedList<K, V>{
        Node head = null;
        Node tail = null;

        //添加Node到链表的尾部
        public void add(Node node){
            if (node == null) {
                return ;
            }
            if (head == null) {
                head = node;
                tail = node;
            }else{
                node.pre = tail;
                node.next = null;
                tail.next = node;
                tail = node;
            }
        }

        //将Node结点移至链表的尾部
        public void removeToTail(Node node){
            if(node == tail || node == null){
                return ;
            }
            if (head == node) {
                head = head.next;
                head.pre = null;
            }else{
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            node.pre = tail;
            node.next = null;
            tail.next = node;
            tail = tail.next;
        }
        //删除链表中的某个Node结点
        public void del(Node node){
            if (node == null) {
                return ;
            }
            if (head == tail && head == node) {
                head = null;
                tail = null;
            }else if (head == node) {
                head = head.next;
                head.pre = null;
            }else if (tail == node) {
                tail = tail.pre;
                tail.next = null;
            }else{
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
        }

        //从头节点删除，也就是最久未被操作的
        public Node delUnusedLonggest(){
            if (head == null) {
                return null;
            }
            Node temp = head;
            if(head == tail){
                head = null;
                tail = null;
            }else{
                head = head.next;
                head.pre = null;
            }
            return temp;
        }
    }

    /**
     * 缓存结构
     * @param <K>
     * @param <V>
     */
    public static class MyCache<K, V>{
        private HashMap<K, Node<K, V>> map;
        private NodeDoubleLinkedList<K, V> list;
        int capacity;

        /**
         * @param capacity  初始化时指定缓存的容量
         */
        public MyCache(int capacity) {
            this.capacity = capacity;
            this.map = new HashMap<>(capacity);
            this.list = new NodeDoubleLinkedList<>();
        }

        //往缓存中set元素
        public void set(K key, V value){
            Node node = new Node<>(key, value);
            if (map.containsKey(key)) {
                map.put(key, node);
                list.removeToTail(node);
                return;
            }
            if (capacity == map.size()) {
                delUnusedlonggest();
            }
            map.put(key, node);
            list.add(node);
        }

        //从缓存中获取元素
        public V get(K key){
            if (!map.containsKey(key)) {
                return null;
            }
            //将操作过的Node移至链表的末尾
            list.removeToTail(map.get(key));
            return map.get(key).value;
        }
        //从缓存中删除元素
        public void del(K key){
            if (!map.containsKey(key)) {
                return ;
            }
            Node<K, V> node = map.remove(key);
            list.del(node);
        }
        //删除最久未被访问的元素
        private void delUnusedlonggest() {
            Node del = list.delUnusedLonggest();
            if (map.containsKey(del.key)) {
                map.remove(del.key);
            }
        }
    }
    public static void main(String[] args) {
        MyCache<String, Integer> testCache = new MyCache<String, Integer>(3);
        testCache.set("A", 1);
        testCache.set("B", 2);
        testCache.set("C", 3);
        System.out.println(testCache.get("B"));
        System.out.println(testCache.get("A"));
        testCache.set("D", 4);
        System.out.println(testCache.get("D"));
        System.out.println(testCache.get("C"));
    }
}
